package 每日一题;

import org.omg.PortableInterceptor.INACTIVE;

import java.util.Arrays;

/**
 * 204. 计数质数
 * 统计所有小于非负整数 n 的质数的数量。
 */

public class Date1203 {
    /**
     * 仿照数学资料
     * 所有大于2的偶数都不是素数，因此我们从3开始找，每次步进2。
     * 判断一个数是否为素数的方法是：判断是否存在小于等于根号n的数能整除n，存在则不是素数，不存在则确定是素数。
     * ====暴力了 超时
     * @param n
     * @return
     */
    public int countPrimes(int n) {

        int count =0;
        if (n<3){
            return 0;
        }

        for (int i=3;i<n;i+=2){
            if (isPrime(i)){
                count++;

            }
            continue;
        }

        return count+1;

    }

    //判断n是不是素数
    public boolean isPrime(int n){
        for (int i =2;i<=Math.sqrt(n);i++){
            if (n % i ==0){
                return false;
            }
            continue;
        }
        return true;
    }


    /**
     * 题解：埃氏筛如果 xx 是质数，那么大于 xx 的 xx 的倍数 2x,3x,\ldots2x,3x,
     * 因此搞一个数组 下标刚好就是要判断的n个数 然后依次判断 如果这个数是素数 那么他的倍数就都是合数
     * @param n
     * @return
     */
    public int countPrimes1(int n) {
        int result=0;
        int[] isPrime = new int[n];
        Arrays.fill(isPrime,1);

        for (int i=2;i<n;i++){
            if (isPrime[i] == 1){
                result++;
                //因为i之前的时候就把所有i的小于i倍数都只为0了 所以就直接从i方开始
                if ((long)i*i<n){
                    for (int j= i*i;j<n;j+=i){
                        isPrime[j]=0;
                    }

                }

            }
        }

        return result;
    }
}
